#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Student
{
	int num;
	char name[50];
	struct Student *next;	
} ;
typedef struct Student student;

student *new(char *name, int num)//创建新的节点
{
	student *newp;
	newp = (student *)malloc(sizeof(student));
	memset(newp, 0, sizeof(newp));
	strcpy(newp->name, name);
	newp->num = num;
	newp->next = NULL;
	return newp;
}

student *addhead(student *listp, student *newp)//表头插入节点 0(1)
{
	newp->next = listp;
	return newp;
}

student *addend(student *listp, student *newp)//表尾插入节点 O(n)
{
	student *p =  NULL;
	p = listp;
	while (p->next != NULL)
	{
		p = p->next;
	}
	p->next = newp;
	return listp;
}

int length(student *listp)//获取链表长度 O(n)
{
	int len = 0;
	while (listp != NULL)
	{
		len++;
		listp = listp->next;
	}
	printf("len: %d\n", len);
	return len;
}


student *lookup(student *listp, char *name)//查找节点 O(n)
{
	for (; listp != NULL; listp = listp->next)
	{
		if (strcmp(name, listp->name) == 0)
			{
				printf("listp->name: %s\n", listp->name);
				return listp;
			}
	}
	printf("can not find the name\n");
	return NULL;
}

void print(student *listp)//打印所以节点 O(n)
{
	while(listp != NULL)
	{
		printf("studentname: %s\n", listp->name);
		printf("studentnum: %d\n", listp->num);
		listp = listp->next;
	}
}

void *delete(student *listp, char *name)//删除节点
{
	student *p1 = NULL;
	student *p2 = NULL;
	p1 = p2 = listp;
	while (p1 != NULL && strcmp(p1->name, name) != 0)
	{
		p2 = p1;
		p1 = p1->next;					
	}
	if (p1 == p2 && p1 == listp)//当要删除的节点是第一个节点的情况
		listp = listp->next;
	else
		p2->next = p1->next;
	free(p1);
	return listp;
}

void freeall(student *listp)
{
	student *next;
	while (listp != NULL)
	{
		next = listp->next;
		free(listp);
		listp = next;
	}
}

int main()
{
	int n;
	int x = 1;
	student *nvlist = NULL;
	student *nvlistp = NULL;
	while (x)
	{
		printf("------------------------------------------------------\n");
		printf("1.create a list\n");
		printf("2.insert a node in head\n");
		printf("3.insert a node in tail\n");
		printf("4.get list length\n");
		printf("5.search a node\n");
		printf("6.print all node\n");
		printf("7.delete a node\n");
		printf("8.delet list\n");
		printf("please input a number\n");
		scanf("%d", &n);
		switch (n)
		{	
			case 1: nvlist = new("liaodao", 42);;break;
			case 2: nvlist = addhead(nvlist, new("lzb", 50));break;
			case 3: nvlist = addend(nvlist, new("ouge", 50));break;
			case 4: length(nvlist);break;
			case 5: nvlistp = lookup(nvlist, "ouge");break;
			case 6: print(nvlist);break;
			case 7: nvlist = delete(nvlist, "lzb");break;
			case 8: freeall(nvlist);break;
			case 0: x = 0; break;
			default: printf("input error!\n");break;
		}
	}
}
